home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqdisplay / render.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-19  |  6.7 KB  |  212 lines
  1. #define    LIBQDISPLAY_CORE
  2. #include "../include/libqdisplay.h"
  3.  
  4. /*
  5.  *   "render" scenes by traversing over the
  6.  *   database, marking already-visited things,
  7.  *   using the PVS information and the "marksurface"
  8.  *   info; use one bsp routine to sort
  9.  */
  10.  
  11. unsigned char *visibleFaces;                    /*[MAX_MAP_FACES / 8 + 1]; */
  12. unsigned char *visibleLeafs;                    /*[MAX_MAP_LEAFS / 8 + 1]; */
  13. unsigned char *visibleNodes;                    /*[MAX_MAP_NODES]; */
  14.  
  15. int model = 0;
  16.  
  17. static bool bbox_inside_plane(register short int *mins, register short int *maxs, register struct extplane *pl)
  18. {
  19.   short int pt[3];
  20.  
  21.   /* use quick test from graphics gems */
  22.   if (pl->positive[0])
  23.     pt[0] = maxs[0];
  24.   else
  25.     pt[0] = mins[0];
  26.  
  27.   if (pl->positive[1])
  28.     pt[1] = maxs[1];
  29.   else
  30.     pt[1] = mins[1];
  31.  
  32.   if (pl->positive[2])
  33.     pt[2] = maxs[2];
  34.   else
  35.     pt[2] = mins[2];
  36.  
  37.   /*
  38.    * each frustum-plane in hesse-form have a positive and a negative half-space
  39.    * we can check if the distance between frustum-plane and point is positive or
  40.    * negative to check where the points is, in the positive or negative
  41.    * half-space
  42.    *
  43.    * if((DotProduct(frustumNormal, point) - frustumDistance) >= 0) -> if(DotProduct(frustumNormal, point) >= frustumDistance)
  44.    *  if is visible (lies in positive half-space)
  45.    * else
  46.    *  it is invisible (lies in negative half-space)
  47.    */
  48.   return DotProduct(pl->normal, pt) >= pl->dist;
  49. }
  50.  
  51. /* is the complete node between the frustum-planes? */
  52. bool node_in_frustrum(register struct dnode_t *node)
  53. {
  54.   if (!bbox_inside_plane(node->mins, node->maxs, &planes[0]) ||
  55.       !bbox_inside_plane(node->mins, node->maxs, &planes[1]) ||
  56.       !bbox_inside_plane(node->mins, node->maxs, &planes[2]) ||
  57.       !bbox_inside_plane(node->mins, node->maxs, &planes[3]))
  58.     return FALSE;
  59.   return TRUE;
  60. }
  61.  
  62. /* is the complete leaf between the frustum-planes? */
  63. bool leaf_in_frustrum(register struct dleaf_t *node)
  64. {
  65.   if (!bbox_inside_plane(node->mins, node->maxs, &planes[0]) ||
  66.       !bbox_inside_plane(node->mins, node->maxs, &planes[1]) ||
  67.       !bbox_inside_plane(node->mins, node->maxs, &planes[2]) ||
  68.       !bbox_inside_plane(node->mins, node->maxs, &planes[3]))
  69.     return FALSE;
  70.   return TRUE;
  71. }
  72.  
  73. /* mark all faces within a given leaf */
  74. void mark_leaf_faces(__memBase, register short int leaf)
  75. {
  76.   int contents = bspMem->shared.quake1.dleafs[leaf].contents;
  77.   short int i = bspMem->shared.quake1.dleafs[leaf].nummarksurfaces;
  78.   unsigned short int *dms = &bspMem->shared.quake1.dmarksurfaces[(int)(bspMem->shared.quake1.dleafs[leaf].firstmarksurface + i)];
  79.  
  80.   for (--i; i >= 0; i--) {
  81.     unsigned short int s = *--dms;
  82.  
  83.     mark_face(s);
  84.   }
  85. }
  86.  
  87. /*
  88.  * The visibility lists are used by BSP Leaves, to
  89.  * determine which other leaves are visible from a given BSP Leaf.
  90.  * The Visibility list can be of size 0, in that case it will not be used.
  91.  * The game will crawl if there is no visibility list in a level.
  92.  *      u_char vislist[numvislist];    / RLE encoded bit array /
  93.  * Basically, the visibility list is an array of bits. There is one such array
  94.  * of bits for each BSP Leaf.  They are all stored in the vislist array, and
  95.  * each leaf has an index to the first byte of it's own array
  96.  * The bit number N, if set to 1, tells that when laying in the tree leaf, one
  97.  * can see the leaf number N.
  98.  * The only complication is that this bit array in run-length encoded:
  99.  * when a set of bytes in the array are all zero, they are coded by zero
  100.  * followed by the number of bytes is the set (always more than 1).
  101.  * Normally, the size of the bit array associated to a leaf should be
  102.  * (numleafs+7)/8, but in fact due to the run length encoding, it's usually
  103.  * much less.
  104.  * When the player is in a leaf, the visibility list is used to tag
  105.  * all the leaves that can possibly be visible, and then only those
  106.  * leaves are rendered.
  107.  * Here is an example of decoding of visibility lists:
  108.  *   / Suppose Leaf is the leaf the player is in. /
  109.  *   v = Leaf.vislist;
  110.  *   for (L = 1; L < numleaves; v++) {
  111.  *     if (visisz[v] == 0) {         / value 0, leaves invisible /
  112.  *       L += 8 * visisz[v + 1]      / skip some leaves /
  113.  *       v++;
  114.  *     }
  115.  *     else {                        / tag 8 leaves, if needed /
  116.  *                                   / examine bits right to left /
  117.  *       for (bit = 1; bit != 0; bit = bit * 2, L++) {
  118.  *         if (visisz[v] & bit)
  119.  *         TagLeafAsVisible(L);
  120.  *       }
  121.  *     }
  122.  *   }
  123.  * Lots of thanks to Tony Myles who fixed the  bit mask formula.
  124.  * There is no necessity to unpack the visibility list in memory,
  125.  * because the code to read them is fast enough.
  126.  */
  127. int visit_visible_leaves(__memBase)
  128. {
  129.   short int n;
  130.   int i;
  131.   unsigned char *vis;
  132.  
  133.   n = find_leaf(bspMem);
  134.  
  135.   if ((!n) || (bspMem->shared.quake1.dleafs[n].visofs < 0)) {
  136.     __memset(visibleLeafs, 0xFF, (bspMem->shared.quake1.dmodels[model].visleafs >> 3) * sizeof(unsigned char));
  137.     return 0;
  138.   }
  139.   else {
  140.     __bzero(visibleLeafs, (bspMem->shared.quake1.dmodels[model].visleafs >> 3) * sizeof(unsigned char));
  141.  
  142.   vis = bspMem->shared.quake1.dvisdata + bspMem->shared.quake1.dleafs[n].visofs;
  143.   for (i = 1; i < bspMem->shared.quake1.dmodels[model].visleafs;) {
  144.     unsigned char v = *vis++;
  145.  
  146.     if (!v) {
  147.       i += *vis++ << 3;                        /* * 8 */
  148.     }
  149.     else {
  150.       if (v & 1)
  151.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  152.       i++;
  153.       if (v & 2)
  154.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  155.       i++;
  156.       if (v & 4)
  157.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  158.       i++;
  159.       if (v & 8)
  160.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  161.       i++;
  162.       if (v & 16)
  163.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  164.       i++;
  165.       if (v & 32)
  166.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  167.       i++;
  168.       if (v & 64)
  169.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  170.       i++;
  171.       if (v & 128)
  172.     visibleLeafs[i >> 3] |= (1 << (i & 7));
  173.       i++;
  174.     }
  175.   }
  176.   return 1;
  177.   }
  178. }
  179.  
  180. /*
  181.  * during a bsp recursion, draw all of the faces
  182.  * stored on this node which are visible (i.e. just
  183.  * test their mark flag)
  184.  */
  185. void render_node_faces(__memBase, register short int node, short register int side)
  186. {
  187.   unsigned short int i, n, f;
  188.  
  189.   n = bspMem->shared.quake1.dnodes[node].numfaces;
  190.   f = bspMem->shared.quake1.dnodes[node].firstface;
  191.  
  192.   for (i = 0; i < n; ++i) {
  193.     if (bspMem->shared.quake1.dfaces[f].side == side)
  194.       if (is_marked_face(f))
  195.     draw_face(bspMem, f);
  196.     unmark_face(f);
  197.     ++f;
  198.   }
  199. }
  200.  
  201. void renderWorld(__memBase)
  202. {
  203.   compute_view_frustrum();
  204.  
  205.   /*for(model = 0; model < bspMem->shared.quake1.nummodels; model++) { */
  206.   visit_visible_leaves(bspMem);
  207.   bsp_find_visible_nodes(bspMem, (short int)bspMem->shared.quake1.dmodels[model].headnode[0]);
  208.   bsp_explore_node(bspMem, (short int)bspMem->shared.quake1.dmodels[model].headnode[0]);
  209.   bsp_render_node(bspMem, (short int)bspMem->shared.quake1.dmodels[model].headnode[0]);
  210.   /*} */
  211. }
  212.